昨天我們寫過了快速排序，不過其實可以對陣列或 List 直接呼叫 Sort 方法。在 .NET Framework 4.5 以前該方法使用快速排序，.NET Framework 4.5 以後 (至後來的 .NET) 皆使用 Introspective Sort(Introsort, 或稱內省排序)，速度也比一般的泡沫排序快很多 ~

Introsort 會依據條件使用 Insertion Sort (插入排序)、Heapsort (堆積排序) 或 Quicksort (快速排序)，以在最壞的狀況下，仍保持 O(NlogN) 的時間複雜度。接下來介紹相關的排序方式：

• Quicksort: 昨天有提到 (Day 5: 用 C# 練習快速排序 - iT 邦幫忙)。
• Insertion Sort: 將資料分成已排序和未排序兩部份，將未排序的資料逐步插入到已排序資料的適當順序，直到沒有未排序資料為止。適合用在資料較少的時候。
• Heapsort: 建立 Max Heap 的二元樹，此時根節點會是最大值，再慢慢地將根節點的值和最右方子節點交換並取出，並重新將最大值移到根節點。重複步驟直到所有節點都被取出。

參考資料

• .NET 陣列用什麼演算法排序？其 Big O 為何？-黑暗執行緒

• Insertion sort (插入排序法). Insertion sort… - by Oliver Liao - Medium

• Day21:[排序演算法]Heap Sort - 堆積排序法 - iT 邦幫忙

• referencesource/mscorlib/system/array.cs at master · microsoft/referencesource · GitHub